{\magonebf 3.11 Dynamic collections of trees  (tree\_collection) }

An instance $D$ of the data type $tree\_collection$ is a collection of 
vertex disjoint rooted trees, each of whose vertices has a real-valued 
cost and contains an information of type $I$, called the information type of
$D$.

\bigskip
{\bf 1. Declaration of a dynamic tree collection type}


\decl tree\_collection I

introduces a new data type with name \name\ consisting of all dynamic
tree collections with information type $I$.



\bigskip
{\bf 2. Creation of a tree\_collection }

\create D {}

creates an instance \var\ of type \name, initialized with the empty collection.



\bigskip
{\bf 3. \operations}

\medskip
\+\cleartabs & \hskip 2truecm & \hskip 5truecm &\cr
\+\op d\_vertex   maketree {I\ x}  
                             {Adds a new tree to $D$ containing a single }
\+\nop                       {vertex $v$ with cost zero and information $x$,}
\+\nop                       {and returns $v$.} 
\smallskip 
\+\op I           inf {d\_vertex\ v} 
                             {Returns the information of vertex $v$.}
\smallskip
\+\op d\_vertex   findroot {d\_vertex\ v} 
                             {Returns the root of the tree containing $v$.}
\smallskip
\+\op d\_vertex   findcost {d\_vertex\ v,\ real\&\ x} {}
\+\nop                       {Sets $x$ to the minimum cost of a vertex on the}
\+\nop                       {tree path from $v$ to findroot($v$) and returns}
\+\nop                       {the last vertex (closest to the root) on this }
\+\nop                       {path of cost $x$.}
\smallskip
\+\op void        addcost {d\_vertex\ v,\ real\ x} {}
\+\nop                       {Adds real number $x$ to the cost of every vertex}
\+\nop                       {on the tree path from $v$ to findroot($v$)}.                                 
\smallskip
\+\op void        link {d\_vertex\ v,\ d\_vertex\ w} {}
\+\nop                   {Combines the trees containing vertices $v$ and $w$}
\+\nop                   {by adding the edge $(v,w)$. (We regard tree }
\+\nop                   {edges as directed from child to parent.) }
\+\nop                   {\precond $v$ and $w$ are in different trees }
\+\nop                   {and $v$ is a root.}
\smallskip
\+\op void        cut {d\_vertex\ v}
                            {Divides the tree containing vertex $v$ into}
\+\nop                      {two trees by deleting the edge out of $v$.}
\+\nop                      {\precond $v$ is not a tree root.}
                                                                      
\bigskip
{\bf 4. Implementation}

Dynamic collections of trees are implemented by partitioning the trees
into vertex disjoint paths and representing each path by a self-adjusting
binary tree (see [T83]). All operations take amortized time $O(\log n)$
where $n$ is the number of maketree operations.


